package leetcode.graph.bfs.p752;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @Title: Solution_v1.java 
 * @Package leetcode.graph.bfs.p752 
 * @Description: 752. 打开转盘锁
 * @author CandyWall   
 * @date 2021年1月18日 上午12:12:42 
 * @version V1.0
 */
class Solution_v2 {
    public int openLock(String[] deadends, String target) {
        
        HashSet<String> deadset = new HashSet<>();
        for(int i = 0; i < deadends.length; i++) {
            deadset.add(deadends[i]);
        }
        
        if(deadset.contains(target)) {
            return -1;
        }
        
        if(deadset.contains("0000")) {
            return -1;
        }
        
        if(target.equals("0000")) {
            return 0;
        }
        
        HashMap<String, Integer> visited = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        visited.put("0000", 0);
        while(!queue.isEmpty()) {
            String curPassword = queue.remove();
            for(String nextPassword : nextPasswords(curPassword)) {
                // 当前密码不在死亡数字序列中，并且没有被遍历过
                if(!deadset.contains(nextPassword) && !visited.containsKey(nextPassword)) {
                    queue.add(nextPassword);
                    visited.put(nextPassword, visited.get(curPassword) + 1);
                    if(nextPassword.equals(target)) {
                        return visited.get(nextPassword);
                    }
                }
            }
        }
        
        return -1;
    }
    
    // 根据当前的密码，调一位以后的密码，一共8种可能
    private ArrayList<String> nextPasswords(String curPassword) {
        ArrayList<String> nextPasswords = new ArrayList<>();
        char[] passwordChar = curPassword.toCharArray();
        for(int i = 0; i < 4; i++) {
            // 记录当前位置的拨轮值
            char tempChar = passwordChar[i];
            // 拨轮加1
            passwordChar[i] = Character.forDigit(((passwordChar[i] - '0' + 1) % 10), 10);
            // 记录拨动当前位的情况
            nextPasswords.add(new String(passwordChar));
            // 当前位置的拨轮值复位
            passwordChar[i] = tempChar;
            // 拨轮减1，减1可以用加9代替
            passwordChar[i] = Character.forDigit(((passwordChar[i] - '0' + 9) % 10), 10);
            // 记录拨动当前位的情况
            nextPasswords.add(new String(passwordChar));
            // 当前位置的拨轮值复位
            passwordChar[i] = tempChar;
        }
        return nextPasswords;
    }
    
    public static void main(String[] args) {
        String[] deadends1 = {"0201","0101","0102","1212","2002"};
        String target = "0202";
        System.out.println(new Solution_v2().openLock(deadends1, target));
        String[] deadends2 = {"8887","8889","8878","8898","8788","8988","7888","9888"};
        target = "8888";
        System.out.println(new Solution_v2().openLock(deadends2, target));
        System.out.println(new Solution_v2().nextPasswords("0000"));
    }
}